package wjl.leetcode;

import wjl.leetcode.Base.ListNode;

/**
 * https://leetcode-cn.com/problems/add-two-numbers/
 * 
 * @author Wjl
 *
 */
public class AddTwoNumbers {
    public static void main( String[] args ) {
        ListNode l1 = new ListNode( 2 );
        l1.next = new ListNode( 4 );
        l1.next.next = new ListNode( 3 );

        ListNode l2 = new ListNode( 5 );
        l2.next = new ListNode( 6 );
        l2.next.next = new ListNode( 4 );
        addTwoNumbers1( l1, l2 );
    }

    /*
     * 执行用时：2 ms, 在所有 Java 提交中击败了99.92%的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了80.71%的用户
     */
    public static ListNode addTwoNumbers1( ListNode l1, ListNode l2 ) {
        int      temp     = 0;
        ListNode rootNode = new ListNode();
        ListNode lastNode = null;
        while (l1 != null || l2 != null){
            int val = 0;
            if ( l1 == null ){
                val = temp + l2.val;
                l2 = l2.next;
            } else if ( l2 == null ){
                val = temp + l1.val;
                l1 = l1.next;
            } else{
                val = l1.val + l2.val + temp;
                l1 = l1.next;
                l2 = l2.next;
            }
            if ( val >= 10 ){
                temp = 1;
                val = val - 10;
            } else{
                temp = 0;
            }
            ListNode curNode = new ListNode( val );
            if ( rootNode.next == null ){
                lastNode = curNode;
                rootNode.next = lastNode;
            } else{
                lastNode.next = curNode;
                lastNode = curNode;
            }
        }
        if ( temp == 1 ){
            lastNode.next = new ListNode( 1 );
        }
        return rootNode.next;
    }

    /*
     * 递归法
     * 执行用时：2 ms, 在所有 Java 提交中击败了99.92%的用户
     * 内存消耗：38.5 MB, 在所有 Java 提交中击败了99.38%的用户
     */
    public static ListNode addTwoNumbers2( ListNode l1, ListNode l2 ) {
        ListNode node = atn2( l1, l2, 0 );
        return node;
    }

    public static ListNode atn2( ListNode l1, ListNode l2, int i ) {
        if ( l1 == null && l2 == null && i == 0 ){
            return null;
        }
        int val = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + i;
        if ( val >= 10 ){
            i = 1;
            val = val - 10;
        } else{
            i = 0;
        }
        ListNode node = new ListNode( val );
        node.next = atn2( l1 != null ? l1.next : null, l2 != null ? l2.next : null, i );
        return node;
    }
}
